#删除有序数组中的重复项 II
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        s = 0
        for f in range(len(nums)):
            if s < 2 or nums[f] != nums[s-2]:
                nums[s] = nums[f]
                s += 1
        return s


#轮转数组
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        nums[:] = nums[-k%n:]+nums[:-k%n]


#买卖股票的最佳时机2
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        a = 0
        for i in range(1, len(prices)):
            t = prices[i] - prices[i-1]
            if t > 0:
                a += t
        return a


#跳跃游戏
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max = 0
        for i, j in enumerate(nums):
            if i <= max and i + j > max:
                max = i + j
        return max >= i


#跳跃游戏2
class Solution:
    def jump(self, nums: List[int]) -> int:
        s, m, e = 0, 0, 0
        for i in range(len(nums)-1):
            m = max(m, nums[i] + i)
            if i == e:
                e = m
                s += 1
        return s


#H指数
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        l, r = 0, n
        while l < r:
            m = (l + r + 1) // 2
            if sum(c >= m for c in citations) >= m:
                l = m
            else:
                r = m - 1
        return r


#O(1) 时间插入、删除和获取随机元素
class RandomizedSet:

    def __init__(self):
        self.nums = []
        self.idx_map = {}


    def insert(self, val: int) -> bool:
        if val not in self.idx_map:
            self.idx_map[val] = len(self.nums)
            self.nums.append(val)
            return True
        return False


    def remove(self, val: int) -> bool:
        if val in self.idx_map:
            s, idx = self.nums[-1], self.idx_map[val]
            self.nums[idx] = s
            self.idx_map[s] = idx
            del self.idx_map[val]
            self.nums.pop()
            return True
        return False


    def getRandom(self) -> int:
        r = random.randint(0,len(self.nums)-1)
        return self.nums[r]



# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()


#除自身以外数组的乘积
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        a = len(nums)
        ans = [1] * a
        j = 1
        for i in range(1,a+1):
            ans[i - 1] *= j
            j *= nums[i-1]

        j = 1
        for i in range(a, 0, -1):
            ans[i-1] *= j
            j *= nums[i-1]

        return ans


#加油站
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        s = 0
        l = 0
        t = 0
        for i in range(len(gas)):
            s = s + gas[i] - cost[i]
            t = t + gas[i] - cost[i]
            if s < 0:
                s = 0
                l = i + 1
        if t < 0:return -1
        return l


#整数转罗马数字
class Solution:
    def intToRoman(self, num: int) -> str:
        hashmap = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}
        res = ''
        for key in hashmap:
            if num //key != 0:
                count = num // key
                res += hashmap[key] * count
                num %= key
        return res